package leetCode.solution;

public class Code02_ThrowChessPiecesProblem {

	public static int solution1(int nLevel, int kChess) {
		if (nLevel < 1 || kChess < 1) {
			return 0;
		}
		int cache[][] = new int[nLevel+1][kChess+1];
		return Process1(nLevel, kChess, cache);
	}

	// rest还剩多少层楼需要去验证
	// k还有多少颗棋子能够使用
	// 一定要验证出最高的不会碎的楼层！但是每次都是坏运气。
	// 返回至少需要扔几次？
	public static int Process1(int rest, int k, int[][] cache) {
		if(cache[rest][k]!=0) {
			return cache[rest][k];
		}
		if (rest == 0) {
			return 0;
		}
		if (k == 1) {
			cache[rest][k] = rest;
			return rest;
		}
		int result = Integer.MAX_VALUE;
		for (int i = 1; i <= rest; i++) {
			// 第i层楼尝试的最大值
			result = Math.min(result, Math.max(Process1(i - 1, k - 1, cache), Process1(rest - i, k, cache)));
		}
		cache[rest][k] = result+1;
		return result + 1;
	}

	// dp
	public static int solution2(int nLevel, int kChess) {
		if (nLevel < 1 || kChess < 1) {
			return 0;
		}
		if (kChess == 1) {
			return nLevel;
		}
		int[][] dp = new int[nLevel + 1][kChess + 1];
		for (int i = 1; i < nLevel + 1; i++) {
			dp[i][1] = i;
		}

		for (int j = 1; j < kChess + 1; j++) {
			dp[1][j] = 1;
		}
		for (int i = 2; i <= nLevel; i++) {
			for (int j = 2; j <= kChess; j++) {
				int min = Integer.MAX_VALUE;
				for (int k = 1; k <= i; k++) {
					// 第i层楼尝试的最大值
					min = Math.min(min, Math.max(dp[k - 1][j - 1], dp[i - k][j]));
				}
				dp[i][j] = min + 1;
			}
		}

		return dp[nLevel][kChess];
	}

	// 四边形不等式
	public static int solution3(int nLevel, int kChess) {
		if (nLevel < 1 || kChess < 1) {
			return 0;
		}
		if (kChess == 1) {
			return nLevel;
		}
		int[][] dp = new int[nLevel + 1][kChess + 1];
		for (int i = 1; i < nLevel + 1; i++) {
			dp[i][1] = i;
		}

		int[][] cands = new int[nLevel + 1][kChess + 1];
		
		for (int j = 1; j < kChess + 1; j++) {
			dp[1][j] = 1;
			cands[1][j]=1;
		}
		for (int i = 2; i <= nLevel; i++) {
			for (int j = kChess; j >= 2; j--) {
				int min = Integer.MAX_VALUE;
				int minEunm = Math.max(1, cands[i-1][j]);
				int maxEunm = j==kChess?(i>>1)+1:Math.min(i, cands[i][j+1]);
				for (int k = minEunm; k <= maxEunm; k++) {
					// 第i层楼尝试的最大值
					int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
					if(cur<=min) {
						min = cur;
						cands[i][j]=k;
					}
				}
				dp[i][j] = min + 1;
			}
		}

		return dp[nLevel][kChess];
	}
	
	// 四边形不等式  一维表 每行复用
	public static int solution4(int nLevel, int kChess) {
		if (nLevel < 1 || kChess < 1) {
			return 0;
		}
		if (kChess == 1) {
			return nLevel;
		}
		int[][] dp = new int[nLevel + 1][kChess + 1];
		for (int i = 1; i != dp.length; i++) {
			dp[i][1] = i;
		}
		int[] cands = new int[kChess + 1];
		for (int i = 1; i != dp[0].length; i++) {
			dp[1][i] = 1;
			cands[i] = 1;
		}
		for (int i = 2; i < nLevel + 1; i++) {
			for (int j = kChess; j > 1; j--) {
				int min = Integer.MAX_VALUE;
				int minEnum = cands[j];
				int maxEnum = j == kChess ? i / 2 + 1 : cands[j + 1];
				for (int k = minEnum; k < maxEnum + 1; k++) {
					int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
					if (cur <= min) {
						min = cur;
						cands[j] = k;
					}
				}
				dp[i][j] = min + 1;
			}
		}
		return dp[nLevel][kChess];
	}

	public static int solution5(int nLevel, int kChess) {
		if (nLevel < 1 || kChess < 1) {
			return 0;
		}
		int bsTimes = log2N(nLevel) + 1;
		if (kChess >= bsTimes) {
			return bsTimes;
		}
		int[] dp = new int[kChess]; //dp[i] 表示i+1个棋子扔res次，可以解决的楼层
		int res = 0; // 次数
		while (true) {
			res++;
			int previous = 0;
			for (int i = 0; i < dp.length; i++) {
				int tmp = dp[i]; // 此时的值时res-1次时能解决的二楼层
				dp[i] = dp[i] + previous + 1;
				previous = tmp;
				if (dp[i] >= nLevel) {
					return res;
				}
			}
		}
	}

	public static int log2N(int n) {
		int res = -1;
		while (n != 0) {
			res++;
			n >>>= 1;
		}
		return res;
	}

	public static void main(String[] args) {

		int nLevel = 50000;
		int kChess = 10;

		long start9 = System.currentTimeMillis();
		System.out.println(solution5(nLevel, kChess));
		long end9 = System.currentTimeMillis();
		System.out.println("cost time: " + (end9 - start9) + " ms");
//		
//		long start1 = System.currentTimeMillis();
//		System.out.println(solution1(nLevel, kChess));
//		long end1 = System.currentTimeMillis();
//		System.out.println("cost time: " + (end1 - start1) + " ms");
		
		long start2 = System.currentTimeMillis();
		System.out.println(solution3(nLevel, kChess));
		long end2 = System.currentTimeMillis();
		System.out.println("cost time: " + (end2 - start2) + " ms");
		
		long start3 = System.currentTimeMillis();
		System.out.println(solution4(nLevel, kChess));
		long end3 = System.currentTimeMillis();
		System.out.println("cost time: " + (end3 - start3) + " ms");

	}

}
